import java.util.*;



public class Day_six {

    //大数相乘
    //描述
    //以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
    //数据范围： 读入的数字大小满足0≤n≤10^1000
    //要求：空间复杂度 O(m)，时间复杂度O(m^2)（假设m是n的长度）
    //示例1
    //输入：
    //"11","99"
    //返回值：
    //"1089"
    //说明：
    //11*99=1089

    //示例2
    //输入：
    //"1","0"
    //返回值：
    //"0"
    public String solve1 (String ss, String tt)
    {
        char[] s = new StringBuffer(ss).reverse().toString().toCharArray();
        char[] t = new StringBuffer(tt).reverse().toString().toCharArray();
        int m = s.length, n = t.length;
        int[] tmp = new int[m + n];
        // 1. ⽆进位相乘相加
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                tmp[i + j] += (s[i] - '0') * (t[j] - '0');
            }
        }
        // 2. 处理进位
        StringBuffer ret = new StringBuffer();
        int c = 0;
        for(int x : tmp)
        {
            c += x;
            ret.append((char)(c % 10 + '0'));
            c /= 10;
        }
        while(c != 0)
        {
            ret.append((char)(c % 10 + '0'));
            c /= 10;
        }
        // 3. 处理前导零
        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0')
        {
            ret.deleteCharAt(ret.length() - 1);
        }
        return ret.reverse().toString();
    }



    //链表相加
    //描述
    //假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
    //给定两个这种链表，请生成代表两个整数相加值的结果链表。
    //数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
    //要求：空间复杂度 O(n)，时间复杂度 O(n)
    //例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
    //
    //示例1
    //输入：
    //[9,3,7],[6,3]
    //返回值：
    //{1,0,0,0}
    //说明：
    //如题面解释

    //示例2
    //输入：
    //[0],[6,3]
    //返回值：
    //{6,3}

    //备注：1≤n,m≤10^6  0≤a[i],b[i]≤9
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val){
            this.val = val;
        }

    }
    // 逆序链表
    public ListNode reserve(ListNode head){
        ListNode newHead = new ListNode(0);
        ListNode cur = head;
        while(cur != null)
        {
            ListNode next = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = next;
        }
        return newHead.next;
    }

    public ListNode addInList (ListNode head1, ListNode head2)
    {
        // 1. 逆序
        head1 = reserve(head1);
        head2 = reserve(head2);
        // 2. ⾼精度加法
        ListNode cur1 = head1, cur2 = head2;
        int t = 0;
        ListNode ret = new ListNode(0), prev = ret;
        while(cur1 != null || cur2 != null || t != 0)
        {
            if(cur1 != null)
            {
                t += cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null)
            {
                t += cur2.val;
                cur2 = cur2.next;
            }
            prev = prev.next = new ListNode(t % 10);
            t /= 10;
        }
        return reserve(ret.next);
    }



    //大数加法（高精度加法)
    //以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
    //数据范围：s.length,t.length≤100000，字符串仅由'0'~‘9’构成
    //要求：时间复杂度O(n)
    //示例1
    //输入：
    //"1","99"
    //返回值：
    //"100"
    //说明：
    //1+99=100

    //示例2
    //输入：
    //"114514",""
    //返回值：
    //"114514"
    public String solve(String s,String t){
        StringBuffer ret = new StringBuffer();
        int tmp = 0;//标记进位 + 本次累加的结果
        int i = s.length() - 1, j = t.length()-1;

        while(i>=0 || j>=0 || tmp>0){
            if (i >= 0){
                tmp += s.charAt(i--) - '0';
            }
            if (j >= 0){
                tmp += t.charAt(j--) - '0';
            }
            ret.append((char)('0' + tmp%10));
            tmp/=10;
        }
        return ret.reverse().toString();//别忘逆序
    }
}
